COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00005 ENDMK
C⊗;
\input macro[1,mps]
\input macrwf[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A05.Tex[262,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, September 7, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Table Search Theorem}
\vskip 1in
Table with $n$ entries placed at random.  $j$ is first vacancy, $k$ is last.
$$\openup1\jot\eqalignno{Pr[j=\alpha]&= {m-\alpha\choose n-\alpha + 1}
\bigg /{m\choose n}\cr
E\biggl [{j\choose p}\biggr ]&= {1\over{m\choose n}}\sum↓j 
{j\choose p}{m-j\choose m-n-1}={m+1\choose m-n+p} \bigg /{m\choose n}\cr
E[j↑{\underline p}]&= p! E\biggl [{j\choose p}\biggr ]= {p! (m+1) 
n↑{\underline{p-1}}\over (m-n+p)↑{\underline p}}\cr
E[j↑{\overline p}]&= p! E\biggl [{j+p-1 \choose p}\biggr ]\cr
&={p!\over {m\choose n}}\sum↓j {j+p-1\choose p}{m-j\choose m-n-1}= p!
{m+p\choose n} \bigg /{m\choose n}\cr
E[j] &= {m+1\over m-n+1}\cr
E[j↑{\underline 2}] &= {2(m+1)n\over (m-n+1)(m-n+2)}\cr
E[j↑{\overline 2}]&= 2 {(m+1)(m+2)\over (m-n+1)(m-n+2)}\cr
V[j] &= E[j↑2]-(E[j])↑2\cr
&= E[j↑{\underline 2}] + E[j] - (E[j])↑2\cr
&= {m+1\over m-n+1}\left ({2n\over m-n+2} + 1 - {m+1\over m-n+1}\right )\cr
&={(m+1)n\over m-n+1}\left ({2\over m-n+2} - {1\over m-n+1}\right ) =
{(m+1) n (m-n)\over (m-n+1)↑2(m-n+2)}\cr
Pr[k=\beta] &= {\beta - 1\choose m-n-1} \bigg /{m\choose n}\cr
E[k↑{\overline p}] &= {1\over {m\choose n}} \sum↓{k\leq m} {k↑{\overline p}(k-1)↑
{\underline {m-n-1}}\over (m-n-1)!}\cr
&={1\over {m\choose n}(m-n-1)!}\sum↓{k\leq m} (k+p-1)↑{\underline {m-n+p-1}}\cr
&={1\over {m\choose n}(m-n-1)!}\,{(m+p)↑{\underline {m-n+p}}\over m-n+p}\cr
&={n!(m-n)! (m+p)!\over m!(m-n-1! n! (m-n+p)}\cr
&={(m+p)! (m-n)\over m! (m-n+p)}\cr
E[k] &= {(m+1)(m-n)\over m-n+1}\cr
E[k↑{\overline 2}] &= {(m+1)(m+2)(m-n)\over m-n+2}\cr
V[k] &= E[k↑{\overline 2}] - E[k] = (E[k])↑2\cr}$$
\bye